T1
个人难度：红 中
按题意模拟即可，平均值就是所有 aia_iai 的总和除以 nnn。
时间复杂度 O(Tn)O(Tn)O(Tn)。
T2
个人难度：橙 下
当 nnn 为偶数时，由平方差公式得：
∑i=0n(−1)i×(n−i)2=n2−(n−1)2+(n−2)2−(n−3)2+...=[n2−(n−1)2]+[(n−2)2−(n−3)2]+...=[n+(n−1)][n−(n−1)]+[(n−2)+(n−3)][(n−2)−(n−3)]+...=n+(n−1)+(n−2)+(n−3)+...=n×(n+1)2.\sum_{i=0}^n (-1)^i\times (n-i)^2\\ = n^2-(n-1)^2+(n-2)^2-(n-3)^2+...\\ = [n^2-(n-1)^2]+[(n-2)^2-(n-3)^2]+...\\ =
[n+(n-1)][n-(n-1)]+[(n-2)+(n-3)][(n-2)-(n-3)]+...\\ =n+(n-1)+(n-2)+(n-3)+...\\ =\dfrac{n\times (n+1)}{2}. i=0∑n (−1)i×(n−i)2=n2−(n−1)2+(n−2)2−(n−3)2+...=[n2−(n−1)2]+[(n−2)2−(n−3)2]+...=[n+(n−1)][n−(n−1)]+[(n−2)+(n−3)][(n−2)−(n−3)]+...=n+(n−1)+(n−2)+(n−3)+...=2n×(n+1) .
奇数同理，结果为 −n×(n+1)2-\dfrac{n\times (n+1)}{2}−2n×(n+1) 。
因为套了一层绝对值，所以输出 n×(n+1)2\dfrac{n\times (n+1)}{2}2n×(n+1) 即可。
注意答案可能会超过 231−12^{31}-1231−1，所以应开 long long。
时间复杂度 O(T)O(T)O(T)。
T3
个人难度：橙 中
注意到本题可以通过 O(2n)O(2^n)O(2n) 的算法，所以我们使用深度优先搜索完成。
时间复杂度 O(2n)O(2^n)O(2n)。
T4
个人难度：橙 上/黄 下
可以发现分组的个数满足单调性，即体力和最小的小组体力和越大，组的数量越少。
所以我们可以二分答案，贪心计算当体力和最小的小组体力和大于等于 midmidmid 时，分组的最少数量是否小于 kkk。
时间复杂度 O(nlog∑ai)O(n\log \sum a_i)O(nlog∑ai )。
T5
个人难度：黄 下
我们可以参考不同的路径_信奥算法普及/提高-_官方-ACGO题库，运用动态规划的思想求得最大值。
注意特殊情况：
这种情况虽然没直接告诉你 (2,2)(2,2)(2,2) 被封死了，但你也不能到达了。
所以我们应该判断它的左边和上面是否都是 0（即到达不了）。
时间复杂度 O(N2)O(N^2)O(N2)。
T6
个人难度：黄 上/绿 下
50PTS
按题意模拟即可。
时间复杂度：O(M)O(M)O(M)。
100PTS
由于在一个点内移动到的点相同，所以在 NNN 步内必定走进一个环，然后就会一直在这个环内循环，如图所示。
D→H→F→JD\rightarrow H \rightarrow F \rightarrow JD→H→F→J 构成了一个环。
而找环也很简单，只需要看看当前的点之前有没有遍历到就行了。
所以答案就是 到达环之前链部分得的分数+遍历整个环得到的分数+剩下的步数获得的分数。
时间复杂度：O(N)O(N)O(N)。
适用范围：M<264M\lt 2^{64}M<264。
100PTS+
我们也可以使用倍增实现。
记 cur[i][j]cur[i][j]cur[i][j] 为在点 jjj 跳 2i2^i2i 格后到达的点，ct[i][j]ct[i][j]ct[i][j] 为在点 jjj 跳 2i2^i2i 格后获得的分数，然后位运算累加即可。由于不是正解，故不多讲解。
时间复杂度：O(NlogM)O(N\log M)O(NlogM)。
适用范围：M<264M\lt 2^{64}M<264。
150PTS
这部分也很简单，只需要把 MMM 转换成高精，编写高精比较，减，除，模低精即可。
时间复杂度：O(N+∣M∣)O(N+|M|)O(N+∣M∣)。
T7
个人难度：绿 中/绿 上
默写一遍zkw线段树模板：
其中这个修改中的len是干什么用的？
没错，计算长度！
我们可以另外开一个线段树，表示每个权值，然后把len改成权值就好了。
我们还可以使用差分数组 O(1)O(1)O(1) 区间查找权值之和，减小查询时间。
注意开快读快写
T8
个人难度：绿 中
根据题意，我们得知：在激活传送点的同时传送至下一个地方是最优的。
因为，如果在路途中传送，对传送点的激活没有贡献，还多花费了时间。
现在，怎么做呢？
例如这张地图：
聪明的你一定可以想到：我们可以构建一个图，如下：
手动构造最优解：
A→B,B→D,D→E,E→F,F→CA\rightarrow B,B \rightarrow D,D \rightarrow E,E \rightarrow F,F \rightarrow CA→B,B→D,D→E,E→F,F→C。
按上面的最优解连边：
可以看出这是这个图的一棵生成树，并且如果这个图中每条边的权值是这两个点对应的传送门之间的距离，那么最优解就是这个图的最小生成树。
接下来就 bfs 出最短路径，接着求最小生成树即可。
时间复杂度：O(NMK)O(NMK)O(NMK)。
